package com.neusoft.search.binary;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 二分查找: 二分查找的前提是目标数组要有序
 * @date 2024-11-21
 */
public class BinarySearch {

    /**
     * 循环二分查找
     *
     * @param arr    目标数组
     * @param target 目标元素
     * @return 返回找到的数据所在数组的索引下标; 未找到返回-1
     */
    public static int cycleBinarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int middleIndex = (startIndex + endIndex) / 2;
            if (arr[middleIndex] == target) {
                return middleIndex;
            } else if (arr[middleIndex] > target) {
                endIndex = middleIndex - 1;
            } else {
                startIndex = middleIndex + 1;
            }
        }

        return -1;
    }

    /**
     * 递归二分查找
     *
     * @param arr    目标数组
     * @param target 目标元素
     * @return 返回找到的数据所在arr数组的索引；未找到返回-1
     */
    public static int recursionBinarySearch(int[] arr, int target) {
        return binarySearch(arr, 0, arr.length - 1, target);
    }

    public static int binarySearch(int[] arr, int leftIndex, int rightIndex, int findVal) {
        if (leftIndex > rightIndex) {
            return -1;
        }
        int middleIndex = (leftIndex + rightIndex) / 2;

        if (findVal > arr[middleIndex]) {
            // 向右递归
            return binarySearch(arr, middleIndex + 1, rightIndex, findVal);
        } else if (findVal < arr[middleIndex]) {
            // 向左递归
            return binarySearch(arr, leftIndex, middleIndex - 1, findVal);
        } else {
            return middleIndex;
        }
    }

}
